1. Field of the Invention
This invention relates to transaction systems for value transfer, and more specifically to improved cryptographic techniques involving publickey digital blind signatures in online value transfers.
2. Description of Prior Art
Of the many proposed electronic payment systems for consumers, only a few allow consumers to ensure that all their transaction data is not linked together into a file on their activities. This property is anticipated to become important in achieving consumer acceptance of automated payment systems, particularly as consumers become more sophisticated about the issues and as systems become more extensive and pervasive.
The underlying technique for allowing consumers to protect their privacy in electronic payments was disclosed in U.S. Pat. No. 4,759,063, titled "Blind Signature Systems," issued to the present applicant, also appearing as European Patent Publication No. 0139313 dated 2/5/85, and which is incorporated herein by reference. A characteristic of these systems is that the payer withdraws money from an account in the form of digital signatures that are later presented in payments. Thus, some provision is needed to at least discourage payers from spending the same digital signature more than once.
For relatively-low-value payments, this "multiple-spending" problem can be addressed by techniques that compromise the privacy of those attempting to show the same signature more than once, as described in the co-pending application of the present applicant, titled "One-Show Blind Signature Systems," filed 3/3/88, with U.S. Ser. No. 168,802, now abandoned.
While such offline techniques may be suitable for a certain segment of payments, the present application is concerned with those other payments requiring the higher security of online verification. For these medium- and higher-value payments, the cost of consulting an online list of already spent digital signatures should be acceptable.
An essential difficulty with currently known online systems, however, is that they generally require a separate digital signature for each denomination. It is believed that one of the most efficient denomination schemes is that based on the powers of two: a one cent digital signature, a two cent signature, a four cent signature, an eight cent signature, and so on. To make a payment, the payer would use the appropriate selection of denominations, much as with coins and bank notes today. For amounts in the neighborhood of $10, for instance, even this binary scheme would entail at least 10 different denominations, approximately half of which would be involved in each payment. For larger amounts, the number of denominations grows logarithmically, so that in the $500 range, 16 denominations are needed, and an average of half are still required for uniformly distributed amounts of payment. When interest is to be earned on value held by the payer, fractional-cent amounts can be needed, further increasing the number of denominations that must be handled.
Of course all these denominations would take up considerable space in a hand-held computer that might be carried by a consumer to the point of sale. They also must be communicated to the retailer and relayed to the payment system provider. Moreover, the system provider must store each of the signatures separately and must look all the signatures submitted for a payment up on the list of already accepted numbers, before giving an O.K. to the shop. Thus, multiple denominations expand the storage and communication costs and might cause appreciable delays.
Additionally, there is the problem of what to do when the payer does not happen to have the proper complement of coins to pay the exact amount, but only a larger amount. It appears then that further signatures would have to be exchanged to return the unspent value. This might also raise the concern that the shop should not be able to improperly obtain the change itself. Furthermore, the complement of coins held by a payer, once revealed, could be used to infer other information about the payer. One thing about which something may be deduced is how much money the payer happens to have at the moment. Another thing revealed might be which other payments could have or could not have made by the particular payer, because of the exact coins involved.